// https://www.lintcode.cn/problem/kill-process/description

class Solution {
public:
    /**
     * @param pid: the process id
     * @param ppid: the parent process id
     * @param kill: a PID you want to kill
     * @return: a list of PIDs of processes that will be killed in the end
     */
    void dfs(map<int, vector<int>>& child, vector<int> &result, int kill)
    {
        // if (child.find(kill) == child.end()) 
        // {
        //     result.push_back(kill); 错的，这样就只能保存叶子节点
        //     return;
        // }
        result.push_back(kill);
        if (child.find(kill) == child.end()) return;
        for (auto r: child[kill])
        {
            dfs(child, result, r);
        }
    }
    vector<int> killProcess(vector<int> &pid, vector<int> &ppid, int kill) {
        map<int, vector<int>> child;
        vector<int> result;
        for (int i = 0; i < pid.size(); ++i)
        {
            if (child.find(ppid[i]) == child.end()) child[ppid[i]] = vector<int>();
            child[ppid[i]].push_back(pid[i]);
        }
        dfs(child, result, kill);
        return result;
    }
};